1. Field of the Invention
This invention is generally relates to computer memory and more specifically to cache memory.
2. Background Art
In the field of information technology, the terms “storage” or “memory” refer to media that retain data for some interval of time, possibly even after electrical power to the computer is turned off. In a business or personal computer system, storage often takes the form of either a hard disk, random access memory (RAM) or cache memory. A hard disk stores the user's files and programs even if the computer is turned off, and has a large capacity. Random Access Memory (RAM) is used to store information such as programs and data temporarily while the computer is using them. RAM can be accessed at very high speeds, which makes it suitable for applications, however RAM used for these purposes is typically volatile and all information in it is lost when the computer is turned off. Cache memory is often built into the microprocessor, hard drives, or other devices and provides high speed dedicated memory to minimize repeated access to slower storage devices.
Caches are common in most computer systems and are used to speed up instruction execution and data retrieval and updates. A memory cache, or “CPU cache,” is a memory bank that bridges main memory and the CPU. A cache is usually either temporary or permanent memory. It is faster than main memory and allows instructions to be executed and data to be read and written at higher speed. Instructions and data are usually transferred from main memory to the cache in blocks. In most cases, the more sequential the instructions in the routine being executed or the more sequential the data being read or written, the greater chance the next required item will already be in the cache, resulting in better performance. Caches serve as temporary staging areas, and their contents are constantly changing.
A “memory cache” or “CPU cache” is a memory bank that bridges main memory and the CPU. It is faster than main memory and allows instructions to be executed and data to be read and written at higher speeds. Instructions and data are usually transferred from main memory to the cache in blocks. A level 1 (L1) cache is a memory bank built into the CPU chip. A level 2 (L2) cache is a secondary staging area that provides data to the L1 cache. L2 cache may be built into the CPU chip, reside on a separate chip in a multi-chip package module or be a separate bank of chips on the motherboard.
A disk cache is a section of main memory or memory on the disk controller board that bridges the disk drive and the CPU. When the disk is read, usually a larger block of data is copied into the cache than is immediately required. If subsequent reads find the data already stored in the cache, there is no need to retrieve it from the disk, which is slower to access. If the cache is used for writing, data are queued up at high speed and then written to disk during idle machine cycles by the caching program. Disk caches are usually just a part of main memory which is usually made up of common dynamic RAM (DRAM) chips, whereas memory caches usually use higher-speed static RAM (SRAM) chips.
The CPU accesses memory according to a distinct hierarchy. Whether data comes from permanent storage such as the hard drive, an input device such as the keyboard or external to the computer system such as over a network, most data is first stored in random access memory (RAM). The CPU then stores pieces of data it will need to access, often in a cache, and maintains certain special data and instructions in the register.
A cache often has two parts, a tag and a data portion. The tag usually contains the index of the datum in main memory which has been cached and information describing the contents in the data portion of the cache. The data portion of a cache is usually significantly larger than the tag portion. Conventional designs all adopt a design such that there are N data entries if there are N tag entries. However, under circumstances, one only needs to keep meta-information in tag entries, and the corresponding data space is wasted.
What is needed is a method to optimize data space while maintaining functionality of the cache.